(define (make-leaf symbol weight)
    (list `leaf symbol weight)
)
(define (leaf? object)
    (eq? (car object) `leaf)
)
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
    (display left)
    (display "-")
    (display right)
    (newline)
    (list 
        left
        right
        (append 
            (symbols left)
            (symbols right)
        )
        (+ (weight left) (weight right))
    )
)

(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)
    )
)
(define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (cadddr tree)
    )
)

(define (adjoin-set x set)
    (cond 
        ((null? set) (list x))
        (< (cadr x) (cadr (car set))
            (cons x set)
        )
        (else 
            (cons 
                (car set)
                (adjoin-set x (cdr set))
            )
        )
    )
)
(define (make-leaf-set pairs)
    (if (null? pairs)
        `()
        (let 
            (
                (pair (car pairs))
            )
            (adjoin-set 
                (make-leaf 
                    (car pair)
                    (cadr pair)
                )
                (make-leaf-set (cdr pairs))
            )
        )
    )
)
(define test-pairs (list  (list `C 1) (list `D 1) (list `B 2) (list `A 4)))
; (display (make-leaf-set test-pairs))
; (newline)

(define (generate-huffman-tree pairs)
    (successive-merge (make-leaf-set pairs))
)

(define (successive-merge set)
    (if (null? (cdr set))
        (car set) 
        (successive-merge
            (adjoin-set 
                (make-code-tree
                    (car set)
                    (cadr set) 
                )
                (cddr set)
            )
        )
    )
)



(display (generate-huffman-tree test-pairs))
(exit)